/**
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 最长无重复子串
 * @param s 
 */

const lengthOfLongestSubstring = (s: string): number => {
    const len = s.length;
    if (len === 0) return 0
    if (len === 1) return 1

    // 存放无重复的子串
    let subStr = s[0]

    let max = 1;
    for (let i = 1; i < len; i++) {
        // 在之前的无重复子串查找和该字符重复的位置
        const repeatIndex = subStr.indexOf(s[i])
        if (repeatIndex > -1) {
            // 找到了, 需要去掉之前的子串
            subStr = subStr.slice(repeatIndex + 1)
        }

        // 加上当前的字符
        subStr += s[i] 

        // 计算最大值
        max = Math.max(max, subStr.length)
    }

    return max;
};



const lengthOfLongestSubstring3 = (s: string): number => {
    const len = s.length;
    if (len === 0) return 0
    if (len === 1) return 1

    // 存储已经出现过的字母的位置
    const map: Record<string, number> = {}

    // 当前无重复子串的长度
    let curLen = 1,
        max = curLen; // 最大长度

    // 表示start到i-1就是最长的无重复子串
    let start = 0
    map[s[0]] = 0
    for (let i = 1; i < len; i++) {
        const cur = s[i]

        const oldSameCharPos = map[cur]
        if (oldSameCharPos !== undefined && oldSameCharPos >= start && oldSameCharPos < i) {
            // 出现重复的, 并且在合法的范围内

            // 重置start
            start = +oldSameCharPos

            // 更改长度
            curLen = i - +oldSameCharPos
        } else {
            // 没出现过
            max = Math.max(++curLen, max)
        }
        map[cur] = i
    }
    return max
};


const lengthOfLongestSubstring2 = (s: string): number => {
    const len = s.length;
    if (len === 0) return 0
    if (len === 1) return 1

    // 当前无重复子串的长度
    let curLen = 1,
        max = curLen; // 最大长度

    // 表示start到i-1就是最长的无重复子串
    let start = 0

    for (let i = 1; i < len; i++) {
        const cur = s[i]
        let hasFind = false
        for (let j = i - 1; j >= start; j--) {
            if (cur === s[j]) {
                // 找到重复的子串

                // 相同了, 直接修改start
                start = j;

                // 修改curLen
                curLen = i - j

                // 标记已经找到了
                hasFind = true

                break;
            }
        }

        // 没找到
        if (!hasFind) {
            max = Math.max(++curLen, max)
        }
    }



    return max
};

console.log(lengthOfLongestSubstring('abcabcbb'))
console.log(lengthOfLongestSubstring('vvvvvvvvvbvvvvv'))
console.log(lengthOfLongestSubstring('pwwkew'))
console.log(lengthOfLongestSubstring("nfpdmpi"))
console.log(lengthOfLongestSubstring("eeydgwdykpv"))